#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct FHQ_Treap
{
    using tree_pair = pair<int, int>;

    struct Node
    {
        int l, r;
        int key;
        int pri;
        int siz;
    } nodes[200005];

    int tot;
    int root;

    void clear()
    {
        tot = 0;
        root = 0;
    }

    void update_size(int u)
    {
        nodes[u].siz = nodes[nodes[u].l].siz + nodes[nodes[u].r].siz + 1;
    }

    tree_pair split(int u, int key)
    {
        if (u == 0)
            return {0, 0};

        if (key < nodes[u].key)
        {
            tree_pair o = split(nodes[u].l, key);
            nodes[u].l = o.second;
            update_size(u);
            return {o.first, u};
        }
        else
        {
            tree_pair o = split(nodes[u].r, key);
            nodes[u].r = o.first;
            update_size(u);
            return {u, o.second};
        }
    }

    int merge(int u, int v)
    {
        if (u == 0)
            return v;
        if (v == 0)
            return u;
        if (nodes[u].pri > nodes[v].pri)
        {
            nodes[u].r = merge(nodes[u].r, v);
            update_size(u);
            return u;
        }
        else
        {
            nodes[v].l = merge(u, nodes[v].l);
            update_size(v);
            return v;
        }
    }

    int create(int key)
    {
        tot++;
        nodes[tot].key = key;
        nodes[tot].pri = rand();
        nodes[tot].siz = 1;
        nodes[tot].l = 0;
        nodes[tot].r = 0;
        return tot;
    }

    void insert(int key)
    {
        tree_pair o = split(root, key);
        o.first = merge(o.first, create(key));
        root = merge(o.first, o.second);
    }

    void erase(int key)
    {
        tree_pair p = split(root, key);
        tree_pair q = split(p.first, key - 1);
        q.second = merge(nodes[q.second].l, nodes[q.second].r);
        root = merge(merge(q.first, q.second), p.second);
    }

    int count(int key)
    {
        tree_pair p = split(root, key);
        tree_pair q = split(p.first, key - 1);
        int ans = q.second;
        root = merge(merge(q.first, q.second), p.second);
        return ans;
    }

    // 返回将 key 插入之后，key 所在的上界排名，实际不插入
    int upper_rank(int key)
    {
        tree_pair o = split(root, key);
        int ans = nodes[o.first].siz;
        root = merge(o.first, o.second);
        return ans + 1;
    }

    // 返回将 key 插入之后，key 所在的下界排名，实际不插入
    int lower_rank(int key)
    {
        tree_pair o = split(root, key - 1);
        int ans = nodes[o.first].siz;
        root = merge(o.first, o.second);
        return ans + 1;
    }
};